<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  
  
  <title>平衡树 Treap（树堆） 学习笔记 | Hexo</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
  <meta name="description" content="新鲜出炉的Treap！">
<meta property="og:type" content="article">
<meta property="og:title" content="平衡树 Treap（树堆） 学习笔记">
<meta property="og:url" content="http://example.com/2022/01/26/%E5%B9%B3%E8%A1%A1%E6%A0%91%20Treap%EF%BC%88%E6%A0%91%E5%A0%86%EF%BC%89%20%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/index.html">
<meta property="og:site_name" content="Hexo">
<meta property="og:description" content="新鲜出炉的Treap！">
<meta property="og:locale" content="en_US">
<meta property="og:image" content="https://s2.loli.net/2022/01/28/uCyoHcIFY6knEVT.png">
<meta property="og:image" content="https://s2.loli.net/2022/01/28/ziYC6AluxGUbDNJ.png">
<meta property="og:image" content="https://s2.loli.net/2022/01/28/dLVUkjP2uIyw9mG.png">
<meta property="og:image" content="https://s2.loli.net/2022/01/27/KLS49Q2rDXuJ7kb.png">
<meta property="og:image" content="https://s2.loli.net/2022/01/29/ZxXsUafCGzN1vye.png">
<meta property="og:image" content="https://s2.loli.net/2022/01/29/E4wmJjHf8DVUBLv.png">
<meta property="article:published_time" content="2022-01-26T15:43:29.410Z">
<meta property="article:modified_time" content="2023-07-19T11:50:28.542Z">
<meta property="article:author" content="John Doe">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://s2.loli.net/2022/01/28/uCyoHcIFY6knEVT.png">
  
    <link rel="alternate" href="/atom.xml" title="Hexo" type="application/atom+xml">
  
  
    <link rel="shortcut icon" href="/favicon.png">
  
  
    
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/typeface-source-code-pro@0.0.71/index.min.css">

  
  
<link rel="stylesheet" href="/css/style.css">

  
    
<link rel="stylesheet" href="/fancybox/jquery.fancybox.min.css">

  
  
<meta name="generator" content="Hexo 6.3.0"></head>

<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/" id="logo">Hexo</a>
      </h1>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"><span class="fa fa-bars"></span></a>
        
          <a class="main-nav-link" href="/">Home</a>
        
          <a class="main-nav-link" href="/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
        
          <a class="nav-icon" href="/atom.xml" title="RSS Feed"><span class="fa fa-rss"></span></a>
        
        <a class="nav-icon nav-search-btn" title="Search"><span class="fa fa-search"></span></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="http://example.com"></form>
      </div>
    </div>
  </div>
</header>

      <div class="outer">
        <section id="main"><article id="post-平衡树 Treap（树堆） 学习笔记" class="h-entry article article-type-post" itemprop="blogPost" itemscope itemtype="https://schema.org/BlogPosting">
  <div class="article-meta">
    <a href="/2022/01/26/%E5%B9%B3%E8%A1%A1%E6%A0%91%20Treap%EF%BC%88%E6%A0%91%E5%A0%86%EF%BC%89%20%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/" class="article-date">
  <time class="dt-published" datetime="2022-01-26T15:43:29.410Z" itemprop="datePublished">2022-01-26</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 class="p-name article-title" itemprop="headline name">
      平衡树 Treap（树堆） 学习笔记
    </h1>
  

      </header>
    
    <div class="e-content article-entry" itemprop="articleBody">
      
        <p>新鲜出炉的Treap！</p>
<p>调了好几个月的 Treap 今天终于调通了，特意写篇博客来纪念一下。</p>
<h1 id="0-Treap-的含义及用途"><a href="#0-Treap-的含义及用途" class="headerlink" title="0. Treap 的含义及用途"></a>0. Treap 的含义及用途</h1><p>在算法竞赛中很多题目要使用二叉搜索树维护信息。然而毒瘤数据可能让二叉搜索树退化成链，这时就需要让二叉搜索树保持平衡，“平衡的”二叉搜索树自然就是“平衡树”啦。“Treap”就是平衡树的一种，由于它易学易写，所以在算法竞赛中很常用。</p>
<p>“Treap” 事英文单词 “Tree” 和 “Heap” 的合成词。顾名思义，它同时拥有树和堆的性质。Treap 每个节点维护两个权值 <code>lev</code> 和 <code>val</code> ,<code>lev</code>是随机分配的，满足堆（本文中指大根堆）性质，<code>val</code> 是 Treap 真正要存储的信息，满足二叉搜索树的性质。像这样：</p>
<p><img src="https://s2.loli.net/2022/01/28/uCyoHcIFY6knEVT.png" alt="屏幕截图 2022-01-27 181828.png"></p>
<p>即节点的<code>val</code>值大于左儿子的<code>val</code>值小于右儿子的<code>val</code>值， <code>lev</code>值大于它的每个儿子的<code>lev</code>值。</p>
<p>这其实是一棵<a target="_blank" rel="noopener" href="https://oi-wiki.org/ds/cartesian-tree/">笛卡尔树</a>。当笛卡尔树的两个权值都确定时，笛卡尔树的形态是唯一的。<del>容易发现，</del>二叉搜索树在数据随机时就是趋近于平衡的，而由于 Treap 的 lev 权值随机，也就是说 Treap 的形态随机，所以 Treap 的平衡也就有了保证。 <del>好不靠谱啊（小声</del></p>
<p>下面博主将结合代码讲解 Treap。</p>
<h1 id="1-操作"><a href="#1-操作" class="headerlink" title="1. 操作"></a>1. 操作</h1><h2 id="1-1-Treap-需要维护的信息"><a href="#1-1-Treap-需要维护的信息" class="headerlink" title="1.-1. Treap 需要维护的信息"></a>1.-1. Treap 需要维护的信息</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line">treap_node pool[MAXN+<span class="number">5</span>];<span class="comment">//内存池</span></span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">treap_node</span>&#123;</span><br><span class="line">    <span class="type">int</span> ls,rs;<span class="comment">//记录左右儿子节点编号</span></span><br><span class="line">    <span class="type">int</span> val;<span class="comment">//treap要维护的信息</span></span><br><span class="line">    <span class="type">int</span> cnt<span class="comment">/*treap内有多少个val，也就是val的副本数*/</span>,siz<span class="comment">/*当前子树大小*/</span>,lev<span class="comment">/*随机权值*/</span>;</span><br><span class="line">&#125;;</span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">treap</span>&#123;</span><br><span class="line">    <span class="type">int</span> root;<span class="comment">//存储树根</span></span><br><span class="line">    <span class="built_in">treap</span>()&#123;</span><br><span class="line">        root=nul;</span><br><span class="line">    &#125;</span><br><span class="line">	<span class="function"><span class="type">void</span> <span class="title">push_up</span><span class="params">(<span class="type">int</span> p)</span></span>&#123;<span class="comment">//维护节点大小信息</span></span><br><span class="line">        pool[p].siz=pool[pool[p].ls].siz+pool[pool[p].rs].siz+pool[p].cnt;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;；</span><br></pre></td></tr></table></figure>
<h2 id="1-0-新建节点、删除节点与垃圾回收"><a href="#1-0-新建节点、删除节点与垃圾回收" class="headerlink" title="1.0. 新建节点、删除节点与垃圾回收"></a>1.0. 新建节点、删除节点与垃圾回收</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line">treap_node pool[MAXN+<span class="number">5</span>];<span class="comment">//内存池</span></span><br><span class="line"><span class="type">int</span> treap_tail;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> nul=<span class="number">0</span>;</span><br><span class="line">queue&lt;<span class="type">int</span>&gt; treap_rubbish;<span class="comment">//“垃圾站”</span></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">new_treap_node</span><span class="params">()</span></span>&#123;<span class="comment">//新建节点</span></span><br><span class="line">    <span class="type">int</span> res=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">if</span>(treap_rubbish.<span class="built_in">empty</span>())&#123;</span><br><span class="line">        res=++treap_tail;</span><br><span class="line">    &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">        res=treap_rubbish.<span class="built_in">front</span>();</span><br><span class="line">        treap_rubbish.<span class="built_in">pop</span>();</span><br><span class="line">    &#125;</span><br><span class="line">    pool[res].cnt=pool[res].siz=pool[res].ls=pool[res].rs=<span class="number">0</span>;</span><br><span class="line">    pool[res].val=<span class="number">0</span>;</span><br><span class="line">    pool[res].lev=<span class="built_in">rand</span>();</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">delete_treap_node</span><span class="params">(<span class="type">int</span> &amp;p)</span></span>&#123;<span class="comment">//删除节点</span></span><br><span class="line">    treap_rubbish.<span class="built_in">push</span>(p);<span class="comment">//回收</span></span><br><span class="line">    p=<span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>博主在这里使用了一个辣鸡版的<a target="_blank" rel="noopener" href="https://oi-wiki.org/contest/common-tricks/#_5">内存池</a>。当删除节点时，可以把废旧的节点编号插入垃圾队列中，这样在下次新建节点时可以直接从垃圾队列里薅一个出来而不用新申请，可以在一定程度上节省空间。</p>
<h2 id="1-1-旋转"><a href="#1-1-旋转" class="headerlink" title="1.1. 旋转"></a>1.1. 旋转</h2><p>在 Treap 中，有时会出现 <code>lev</code> 的堆性质被破坏的现象，这时就需要用“旋转”操作来维护堆性质的同时不破坏二叉搜索树性质。例如这种情况：</p>
<p><img src="https://s2.loli.net/2022/01/28/ziYC6AluxGUbDNJ.png" alt="屏幕截图 2022-01-28 101702.png"></p>
<p>我们可以通过“左旋”来维护它。如图：</p>
<p><img src="https://s2.loli.net/2022/01/28/dLVUkjP2uIyw9mG.png" alt="屏幕截图 2022-01-28 102707.png"></p>
<p>我们惊奇地发现，“左旋”操作在没有破坏二叉搜索树性质的前提下颠倒了节点<code>A</code>和节点<code>B</code>的父子关系！</p>
<p>“左旋”操作代码：<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">void</span> <span class="title">zag</span><span class="params">(<span class="type">int</span> &amp;p)</span></span>&#123;<span class="comment">//由于此操作可能更改当前子树的根节点，所以要使用引用来确保p永远指向当前子树的根节点</span></span><br><span class="line">    <span class="type">int</span> tmp=pool[p].rs;</span><br><span class="line">    pool[p].rs=pool[tmp].ls;</span><br><span class="line">    pool[tmp].ls=p;</span><br><span class="line">    <span class="built_in">push_up</span>(p);<span class="built_in">push_up</span>(tmp);</span><br><span class="line">    p=tmp;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>同样的，也存在一个右旋操作，代码如下：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">void</span> <span class="title">zig</span><span class="params">(<span class="type">int</span> &amp;p)</span></span>&#123;</span><br><span class="line">    <span class="type">int</span> tmp=pool[p].ls;</span><br><span class="line">    pool[p].ls=pool[tmp].rs;</span><br><span class="line">    pool[tmp].rs=p;</span><br><span class="line">    <span class="built_in">push_up</span>(p);<span class="built_in">push_up</span>(tmp);</span><br><span class="line">    p=tmp;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><del>容易发现，</del>左旋和右旋是相反的操作。如图：</p>
<p><img src="https://s2.loli.net/2022/01/27/KLS49Q2rDXuJ7kb.png" alt="屏幕截图 2022-01-27 155646.png"></p>
<p>有了旋转操作，我们就可以在不破坏<code>val</code>的二叉搜索树性质的条件下维护<code>lev</code>的堆性质了。</p>
<p>有一个细节：由于旋转后当前子树的树根会改变，所以在<code>zig</code>和<code>zag</code>函数中参数<code>p</code>要传引用以方便修改<code>p</code>。</p>
<h2 id="1-3-插入与删除"><a href="#1-3-插入与删除" class="headerlink" title="1.3. 插入与删除"></a>1.3. 插入与删除</h2><p>Treap 的插入操作和普通二叉搜索树差不多，只不过如果在插入过程中堆性质被破坏要通过旋转来维护。代码如下：<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">void</span> <span class="title">insert</span><span class="params">(<span class="type">int</span> &amp;p,<span class="type">int</span> x)</span></span>&#123;<span class="comment">//插入</span></span><br><span class="line">    <span class="keyword">if</span>(p==nul)&#123;<span class="comment">//如果没有值为x节点就新建一个</span></span><br><span class="line">        p=<span class="built_in">new_treap_node</span>();</span><br><span class="line">        pool[p].val=x;</span><br><span class="line">        pool[p].siz=pool[p].cnt=<span class="number">1</span>;</span><br><span class="line">    &#125;<span class="keyword">else</span> <span class="keyword">if</span>(x==pool[p].val)&#123;<span class="comment">//如果找到值为x节点就让副本数++</span></span><br><span class="line">        pool[p].cnt++;</span><br><span class="line">        <span class="built_in">push_up</span>(p);</span><br><span class="line">    &#125;<span class="keyword">else</span> <span class="keyword">if</span>(x&lt;pool[p].val)&#123;<span class="comment">//递归</span></span><br><span class="line">        <span class="built_in">insert</span>(pool[p].ls,x);</span><br><span class="line">        <span class="built_in">push_up</span>(p);</span><br><span class="line">        <span class="keyword">if</span>(pool[pool[p].ls].lev&gt;pool[p].lev)<span class="built_in">zig</span>(p);<span class="comment">//通过旋转维护lev的堆性质</span></span><br><span class="line">    &#125;<span class="keyword">else</span>&#123;<span class="comment">//x&gt;pool[p].val</span></span><br><span class="line">        <span class="built_in">insert</span>(pool[p].rs,x);</span><br><span class="line">        <span class="built_in">push_up</span>(p);</span><br><span class="line">        <span class="keyword">if</span>(pool[pool[p].rs].lev&gt;pool[p].lev)<span class="built_in">zag</span>(p);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>Treap 的删除操作稍微复杂亿点。由于 Treap 恶心的堆性质，所以在删除节点时要采取把节点旋转成叶子再直接删除的方式删除节点。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">void</span> <span class="title">erase</span><span class="params">(<span class="type">int</span> &amp;p,<span class="type">int</span> x)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(p==nul)&#123;<span class="comment">//没有值为x的节点就没有删除的必要了</span></span><br><span class="line">    &#125;<span class="keyword">else</span> <span class="keyword">if</span>(x==pool[p].val)&#123;<span class="comment">//如果要删除当前节点</span></span><br><span class="line">        <span class="keyword">if</span>(pool[p].cnt&gt;<span class="number">1</span>)&#123;<span class="comment">//如果有多个副本就副本数--</span></span><br><span class="line">            pool[p].cnt--;<span class="built_in">push_up</span>(p);</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;<span class="comment">//如果只有1个副本就必须删除当前节点</span></span><br><span class="line">            pool[p].cnt=<span class="number">0</span>;</span><br><span class="line">            <span class="keyword">if</span>(!(pool[p].ls||pool[p].rs))&#123;<span class="comment">//如果当前节点是叶子就直接删除</span></span><br><span class="line">                <span class="built_in">delete_treap_node</span>(p);</span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;<span class="comment">//否则往下转</span></span><br><span class="line">                <span class="comment">//为满足堆性质要判断应该让左儿子还是右儿子“当爹”</span></span><br><span class="line">                <span class="keyword">if</span>(pool[p].rs==<span class="number">0</span>||<span class="comment">//只有左儿子</span></span><br><span class="line">                (pool[p].ls&amp;&amp;pool[pool[p].ls].lev&gt;pool[pool[p].rs].lev))&#123;<span class="comment">//左儿子大于右儿子</span></span><br><span class="line">                    <span class="built_in">zig</span>(p);<span class="comment">//让左儿子“当爹”</span></span><br><span class="line">                    <span class="built_in">erase</span>(pool[p].rs,x);<span class="comment">//当前节点转到了右儿子上，继续“追杀”</span></span><br><span class="line">                &#125;<span class="keyword">else</span>&#123;<span class="comment">//同理</span></span><br><span class="line">                    <span class="built_in">zag</span>(p);</span><br><span class="line">                    <span class="built_in">erase</span>(pool[p].ls,x);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;<span class="keyword">else</span> <span class="keyword">if</span>(x&lt;pool[p].val)&#123;<span class="comment">//递归</span></span><br><span class="line">        <span class="built_in">erase</span>(pool[p].ls,x);</span><br><span class="line">        <span class="built_in">push_up</span>(p);</span><br><span class="line">        <span class="keyword">if</span>(pool[p].ls&amp;&amp;pool[pool[p].ls].lev&gt;pool[p].lev)<span class="built_in">zig</span>(p);</span><br><span class="line">    &#125;<span class="keyword">else</span>&#123;<span class="comment">//x&gt;pool[p].val</span></span><br><span class="line">        <span class="built_in">erase</span>(pool[p].rs,x);</span><br><span class="line">        <span class="built_in">push_up</span>(p);</span><br><span class="line">        <span class="keyword">if</span>(pool[p].rs&amp;&amp;pool[pool[p].rs].lev&gt;pool[p].lev)<span class="built_in">zag</span>(p);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="1-4-其他查找操作"><a href="#1-4-其他查找操作" class="headerlink" title="1.4. 其他查找操作"></a>1.4. 其他查找操作</h2><p>Treap 的查找操作跟普通的二叉搜索树相同，这里不再赘述，直接放代码：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">int</span> <span class="title">rank</span><span class="params">(<span class="type">int</span> p,<span class="type">int</span> x)</span></span>&#123;<span class="comment">//查询比x小的数的个数+1</span></span><br><span class="line">    <span class="keyword">if</span>(p==nul)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    &#125;<span class="keyword">else</span> <span class="keyword">if</span>(x==pool[p].val)&#123;</span><br><span class="line">        <span class="keyword">return</span> pool[pool[p].ls].siz+<span class="number">1</span>;</span><br><span class="line">    &#125;<span class="keyword">else</span> <span class="keyword">if</span>(x&lt;pool[p].val)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">rank</span>(pool[p].ls,x);</span><br><span class="line">    &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">        <span class="keyword">return</span> pool[pool[p].ls].siz+pool[p].cnt+<span class="built_in">rank</span>(pool[p].rs,x);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">kth</span><span class="params">(<span class="type">int</span> p,<span class="type">int</span> x)</span></span>&#123;<span class="comment">//查询第x小的树</span></span><br><span class="line">    <span class="keyword">if</span>(p==nul)&#123;</span><br><span class="line">        <span class="keyword">return</span> INF;</span><br><span class="line">    &#125;<span class="keyword">else</span> <span class="keyword">if</span>(pool[pool[p].ls].siz&gt;=x)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">kth</span>(pool[p].ls,x);</span><br><span class="line">    &#125;<span class="keyword">else</span> <span class="keyword">if</span>(pool[pool[p].ls].siz+pool[p].cnt&gt;=x)&#123;</span><br><span class="line">        <span class="keyword">return</span> pool[p].val;</span><br><span class="line">    &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">kth</span>(pool[p].rs,x-pool[pool[p].ls].siz-pool[p].cnt);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">count</span><span class="params">(<span class="type">int</span> p,<span class="type">int</span> x)</span></span>&#123;<span class="comment">//查询x有多少个</span></span><br><span class="line">    <span class="keyword">if</span>(p==nul)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;<span class="keyword">else</span> <span class="keyword">if</span>(x==pool[p].val)&#123;</span><br><span class="line">        <span class="keyword">return</span> pool[p].cnt;</span><br><span class="line">    &#125;<span class="keyword">else</span> <span class="keyword">if</span>(x&lt;pool[p].val)&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">count</span>(pool[p].ls,x);</span><br><span class="line">    &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="built_in">count</span>(pool[p].rs,x);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h1 id="2-Treap-的应用"><a href="#2-Treap-的应用" class="headerlink" title="2. Treap 的应用"></a>2. Treap 的应用</h1><p>Treap 可以维护很多信息，还可以扩展到树套树、可持久化等神奇科技。总之，Treap 十分实用。</p>
<h1 id="3-坑点与吐槽"><a href="#3-坑点与吐槽" class="headerlink" title="3. 坑点与吐槽"></a>3. 坑点与吐槽</h1><ol>
<li>Treap 的旋转操作十分毒瘤，如果在考场上忘了怎么写可以把<a target="_blank" rel="noopener" href="https://sm.ms/image/KLS49Q2rDXuJ7kb">这张图</a>画一画。</li>
<li>一定要考虑边界情况！一定要考虑边界情况！一定要考虑边界情况！</li>
<li>一定要随手<code>push_up</code>！</li>
<li>Treap 的模板题博主调了甚至几个月才调出来（我太菜了QAQ）。如图：<img src="https://s2.loli.net/2022/01/29/ZxXsUafCGzN1vye.png" alt="屏幕截图 2022-01-29 095604.png"><img src="https://s2.loli.net/2022/01/29/E4wmJjHf8DVUBLv.png" alt="屏幕截图 2022-01-29 095621.png"><del>我真有毅力（小声</del></li>
</ol>
<h1 id="4-完整代码"><a href="#4-完整代码" class="headerlink" title="4. 完整代码"></a>4. 完整代码</h1><p>最后，附赠一份能通过模板题<a target="_blank" rel="noopener" href="https://www.luogu.com.cn/problem/P3369">洛谷P3369</a>的代码：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="meta">#<span class="keyword">define</span> MAXN 100000</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> INF 0x3fffffff</span></span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">treap_node</span>&#123;</span><br><span class="line">    <span class="type">int</span> ls,rs;</span><br><span class="line">    <span class="type">int</span> val;</span><br><span class="line">    <span class="type">int</span> cnt,siz,lev;</span><br><span class="line">&#125;;</span><br><span class="line">treap_node pool[MAXN+<span class="number">5</span>];</span><br><span class="line"><span class="type">int</span> treap_tail;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> nul=<span class="number">0</span>;</span><br><span class="line">queue&lt;<span class="type">int</span>&gt; treap_rubbish;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">new_treap_node</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="type">int</span> res=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">if</span>(treap_rubbish.<span class="built_in">empty</span>())&#123;</span><br><span class="line">        res=++treap_tail;</span><br><span class="line">    &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">        res=treap_rubbish.<span class="built_in">front</span>();</span><br><span class="line">        treap_rubbish.<span class="built_in">pop</span>();</span><br><span class="line">    &#125;</span><br><span class="line">    pool[res].cnt=pool[res].siz=pool[res].ls=pool[res].rs=<span class="number">0</span>;</span><br><span class="line">    pool[res].val=<span class="number">0</span>;</span><br><span class="line">    pool[res].lev=<span class="built_in">rand</span>();</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">delete_treap_node</span><span class="params">(<span class="type">int</span> &amp;p)</span></span>&#123;</span><br><span class="line">    treap_rubbish.<span class="built_in">push</span>(p);</span><br><span class="line">    p=<span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">treap</span>&#123;</span><br><span class="line">    <span class="type">int</span> root;</span><br><span class="line">    <span class="built_in">treap</span>()&#123;</span><br><span class="line">        root=nul;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="type">void</span> <span class="title">zig</span><span class="params">(<span class="type">int</span> &amp;p)</span></span>&#123;</span><br><span class="line">        <span class="type">int</span> tmp=pool[p].ls;</span><br><span class="line">        pool[p].ls=pool[tmp].rs;</span><br><span class="line">        pool[tmp].rs=p;</span><br><span class="line">        <span class="built_in">push_up</span>(p);<span class="built_in">push_up</span>(tmp);</span><br><span class="line">        p=tmp;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="type">void</span> <span class="title">zag</span><span class="params">(<span class="type">int</span> &amp;p)</span></span>&#123;</span><br><span class="line">        <span class="type">int</span> tmp=pool[p].rs;</span><br><span class="line">        pool[p].rs=pool[tmp].ls;</span><br><span class="line">        pool[tmp].ls=p;</span><br><span class="line">        <span class="built_in">push_up</span>(p);<span class="built_in">push_up</span>(tmp);</span><br><span class="line">        p=tmp;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="type">void</span> <span class="title">push_up</span><span class="params">(<span class="type">int</span> p)</span></span>&#123;</span><br><span class="line">        pool[p].siz=pool[pool[p].ls].siz+pool[pool[p].rs].siz+pool[p].cnt;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="type">void</span> <span class="title">insert</span><span class="params">(<span class="type">int</span> &amp;p,<span class="type">int</span> x)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(p==nul)&#123;</span><br><span class="line">            p=<span class="built_in">new_treap_node</span>();</span><br><span class="line">            pool[p].val=x;</span><br><span class="line">            pool[p].siz=pool[p].cnt=<span class="number">1</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(x==pool[p].val)&#123;</span><br><span class="line">            pool[p].cnt++;</span><br><span class="line">            <span class="built_in">push_up</span>(p);</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(x&lt;pool[p].val)&#123;</span><br><span class="line">            <span class="built_in">insert</span>(pool[p].ls,x);</span><br><span class="line">            <span class="built_in">push_up</span>(p);</span><br><span class="line">            <span class="keyword">if</span>(pool[pool[p].ls].lev&gt;pool[p].lev)<span class="built_in">zig</span>(p);</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;<span class="comment">//x&gt;pool[p].val</span></span><br><span class="line">            <span class="built_in">insert</span>(pool[p].rs,x);</span><br><span class="line">            <span class="built_in">push_up</span>(p);</span><br><span class="line">            <span class="keyword">if</span>(pool[pool[p].rs].lev&gt;pool[p].lev)<span class="built_in">zag</span>(p);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="type">void</span> <span class="title">erase</span><span class="params">(<span class="type">int</span> &amp;p,<span class="type">int</span> x)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(p==nul)&#123;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(x==pool[p].val)&#123;</span><br><span class="line">            <span class="keyword">if</span>(pool[p].cnt&gt;<span class="number">1</span>)&#123;</span><br><span class="line">                pool[p].cnt--;<span class="built_in">push_up</span>(p);</span><br><span class="line">            &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                pool[p].cnt=<span class="number">0</span>;</span><br><span class="line">                <span class="keyword">if</span>(!(pool[p].ls||pool[p].rs))&#123;</span><br><span class="line">                    <span class="built_in">delete_treap_node</span>(p);</span><br><span class="line">                &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                    <span class="keyword">if</span>(pool[p].rs==<span class="number">0</span>||</span><br><span class="line">                    (pool[p].ls&amp;&amp;pool[pool[p].ls].lev&gt;pool[pool[p].rs].lev))&#123;</span><br><span class="line">                        <span class="built_in">zig</span>(p);</span><br><span class="line">                        <span class="built_in">erase</span>(pool[p].rs,x);</span><br><span class="line">                    &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">                        <span class="built_in">zag</span>(p);</span><br><span class="line">                        <span class="built_in">erase</span>(pool[p].ls,x);</span><br><span class="line">                    &#125;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(x&lt;pool[p].val)&#123;</span><br><span class="line">            <span class="built_in">erase</span>(pool[p].ls,x);</span><br><span class="line">            <span class="built_in">push_up</span>(p);</span><br><span class="line">            <span class="keyword">if</span>(pool[p].ls&amp;&amp;pool[pool[p].ls].lev&gt;pool[p].lev)<span class="built_in">zig</span>(p);</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;<span class="comment">//x&gt;pool[p].val</span></span><br><span class="line">            <span class="built_in">erase</span>(pool[p].rs,x);</span><br><span class="line">            <span class="built_in">push_up</span>(p);</span><br><span class="line">            <span class="keyword">if</span>(pool[p].rs&amp;&amp;pool[pool[p].rs].lev&gt;pool[p].lev)<span class="built_in">zag</span>(p);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">rank</span><span class="params">(<span class="type">int</span> p,<span class="type">int</span> x)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(p==nul)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(x==pool[p].val)&#123;</span><br><span class="line">            <span class="keyword">return</span> pool[pool[p].ls].siz+<span class="number">1</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(x&lt;pool[p].val)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="built_in">rank</span>(pool[p].ls,x);</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="keyword">return</span> pool[pool[p].ls].siz+pool[p].cnt+<span class="built_in">rank</span>(pool[p].rs,x);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">kth</span><span class="params">(<span class="type">int</span> p,<span class="type">int</span> x)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(p==nul)&#123;</span><br><span class="line">            <span class="keyword">return</span> INF;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(pool[pool[p].ls].siz&gt;=x)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="built_in">kth</span>(pool[p].ls,x);</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(pool[pool[p].ls].siz+pool[p].cnt&gt;=x)&#123;</span><br><span class="line">            <span class="keyword">return</span> pool[p].val;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="built_in">kth</span>(pool[p].rs,x-pool[pool[p].ls].siz-pool[p].cnt);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="type">int</span> <span class="title">count</span><span class="params">(<span class="type">int</span> p,<span class="type">int</span> x)</span></span>&#123;</span><br><span class="line">        <span class="keyword">if</span>(p==nul)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(x==pool[p].val)&#123;</span><br><span class="line">            <span class="keyword">return</span> pool[p].cnt;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(x&lt;pool[p].val)&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="built_in">count</span>(pool[p].ls,x);</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="built_in">count</span>(pool[p].rs,x);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="built_in">srand</span>(<span class="number">19260817</span>);</span><br><span class="line">    treap a;</span><br><span class="line">    <span class="type">int</span> n;cin&gt;&gt;n;</span><br><span class="line">    <span class="keyword">while</span>(n--)&#123;</span><br><span class="line">        <span class="type">int</span> op,x;cin&gt;&gt;op&gt;&gt;x;</span><br><span class="line">        <span class="keyword">if</span>(op==<span class="number">1</span>)&#123;</span><br><span class="line">            a.<span class="built_in">insert</span>(a.root,x);</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(op==<span class="number">2</span>)&#123;</span><br><span class="line">            a.<span class="built_in">erase</span>(a.root,x);</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(op==<span class="number">3</span>)&#123;</span><br><span class="line">            cout&lt;&lt;a.<span class="built_in">rank</span>(a.root,x)&lt;&lt;endl;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(op==<span class="number">4</span>)&#123;</span><br><span class="line">            cout&lt;&lt;a.<span class="built_in">kth</span>(a.root,x)&lt;&lt;endl;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(op==<span class="number">5</span>)&#123;</span><br><span class="line">            cout&lt;&lt;a.<span class="built_in">kth</span>(a.root,a.<span class="built_in">rank</span>(a.root,x)<span class="number">-1</span>)&lt;&lt;endl;</span><br><span class="line">        &#125;<span class="keyword">else</span> <span class="keyword">if</span>(op==<span class="number">6</span>)&#123;</span><br><span class="line">            cout&lt;&lt;a.<span class="built_in">kth</span>(a.root,a.<span class="built_in">rank</span>(a.root,x)+a.<span class="built_in">count</span>(a.root,x))&lt;&lt;endl;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h6 id="5-点一个赞！"><a href="#5-点一个赞！" class="headerlink" title="5.点一个赞！"></a><del>5.点一个赞！</del></h6>
      
    </div>
    <footer class="article-footer">
      <a data-url="http://example.com/2022/01/26/%E5%B9%B3%E8%A1%A1%E6%A0%91%20Treap%EF%BC%88%E6%A0%91%E5%A0%86%EF%BC%89%20%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/" data-id="clk9o8ln6000c8wi5g0mohcsx" data-title="平衡树 Treap（树堆） 学习笔记" class="article-share-link"><span class="fa fa-share">Share</span></a>
      
      
      
    </footer>
  </div>
  
    
<nav id="article-nav">
  
    <a href="/2022/02/11/%E4%B8%BB%E5%B8%AD%E6%A0%91%E3%80%81%E5%87%BD%E6%95%B0%E5%BC%8F%E7%BA%BF%E6%AE%B5%E6%A0%91%E3%80%81%E5%8F%AF%E6%8C%81%E4%B9%85%E5%8C%96%E7%BA%BF%E6%AE%B5%E6%A0%91%20%E5%88%9D%E6%AD%A5%20%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/" id="article-nav-newer" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Newer</strong>
      <div class="article-nav-title">
        
          主席树、函数式线段树、可持久化线段树 初步 学习笔记
        
      </div>
    </a>
  
  
    <a href="/2022/01/15/%E8%BE%B9%E5%B8%A6%E6%9D%83%E5%B9%B6%E6%9F%A5%E9%9B%86%20%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0%20&amp;%20%E6%B4%9B%E8%B0%B7P1196%20%E3%80%8CNOI2002%E3%80%8D%20%E9%93%B6%E6%B2%B3%E8%8B%B1%E9%9B%84%E4%BC%A0%E8%AF%B4%20%E9%A2%98%E8%A7%A3/" id="article-nav-older" class="article-nav-link-wrap">
      <strong class="article-nav-caption">Older</strong>
      <div class="article-nav-title">边带权并查集 学习笔记 &amp;amp; 洛谷P1196 「NOI2002」 银河英雄传说 题解</div>
    </a>
  
</nav>

  
</article>


</section>
        
          <aside id="sidebar">
  
    

  
    

  
    
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Archives</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2023/07/">July 2023</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2022/10/">October 2022</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2022/05/">May 2022</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2022/02/">February 2022</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2022/01/">January 2022</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/08/">August 2021</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/07/">July 2021</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2021/06/">June 2021</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2020/08/">August 2020</a></li></ul>
    </div>
  </div>


  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Recent Posts</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/2023/07/17/%E5%86%B3%E7%AD%96%E5%8D%95%E8%B0%83%E6%80%A7%E4%BC%98%E5%8C%96DP%20%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0%20AND%20P4767%20%E3%80%8CIOI2000%E3%80%8D%20%E9%82%AE%E5%B1%80%20%E9%A2%98%E8%A7%A3/">决策单调性优化DP 学习笔记 AND P4767 「IOI2000」 邮局 题解</a>
          </li>
        
          <li>
            <a href="/2022/10/30/CSP-S%202022%20%E6%B8%B8%E8%AE%B0/">CSP-S 2022 游记</a>
          </li>
        
          <li>
            <a href="/2022/05/29/%E6%96%9C%E7%8E%87%E4%BC%98%E5%8C%96%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%20%E5%AD%A6%E4%B9%A0%E7%AC%94%E8%AE%B0/">斜率优化动态规划 学习笔记</a>
          </li>
        
          <li>
            <a href="/2022/05/22/PKUSC%E4%B8%80%E5%8F%A5%E8%AF%9D%E6%B8%B8%E8%AE%B0/">PKUSC一句话游记</a>
          </li>
        
          <li>
            <a href="/2022/05/18/%E7%9C%81%E9%80%89%E6%B8%B8%E8%AE%B0%EF%BC%9F%E7%9C%81%E9%80%89%E6%B8%B8%E5%AF%84%EF%BC%81/">省选游记？省选游寄！</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      
      &copy; 2023 John Doe<br>
      Powered by <a href="https://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer>

    </div>
    <nav id="mobile-nav">
  
    <a href="/" class="mobile-nav-link">Home</a>
  
    <a href="/archives" class="mobile-nav-link">Archives</a>
  
</nav>
    


<script src="/js/jquery-3.6.4.min.js"></script>



  
<script src="/fancybox/jquery.fancybox.min.js"></script>




<script src="/js/script.js"></script>





  </div>
</body>
</html>